#include <cmath>
#include <iostream>
#include <stack>
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

/**
 * @方法: st 算法
 * @时间复杂度: O(n logn)
 * @空间复杂度: O()
 * @评价:
 */
int dp[1005][10];
TreeNode* build(vector<int>& nums, int begin, int end) {
    if (begin > end) return nullptr;
    int k = log2(end - begin + 1);
    int mx = nums[dp[begin][k]] > nums[dp[end - (1 << k) + 1][k]] ? dp[begin][k]
                                                                  : dp[end - (1 << k) + 1][k];
    TreeNode* root = new TreeNode(nums[mx]);
    root->left = build(nums, begin, mx - 1);
    root->right = build(nums, mx + 1, end);
    return root;
}
TreeNode* constructMaximumBinaryTree1(vector<int>& nums) {
    for (int i = 0; i < nums.size(); i++) dp[i][0] = i;
    for (int j = 1; (1 << j) <= nums.size(); j++) {
        for (int i = 0; i + (1 << (j - 1)) < nums.size(); i++) {
            dp[i][j] = nums[dp[i][j - 1]] > nums[dp[i + (1 << (j - 1))][j - 1]]
                           ? dp[i][j - 1]
                           : dp[i + (1 << (j - 1))][j - 1];
        }
    }
    return build(nums, 0, nums.size() - 1);
}

/**
 * @方法: 单调栈
 * @时间复杂度: O(n)
 * @空间复杂度: O(n)
 * @评价:
 */
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
    stack<int> stk;
    vector<TreeNode*> nodes(nums.size());
    vector<int> left(nums.size(), -1);
    vector<int> right(nums.size(), -1);
    for (int i = 0; i < nums.size(); i++) {
        nodes[i] = new TreeNode(nums[i]);
        while (!stk.empty() && nums[stk.top()] < nums[i]) {
            right[stk.top()] = i;
            stk.pop();
        }
        if (!stk.empty()) left[i] = stk.top();
        stk.push(i);
    }
    TreeNode* root;
    for (int i = 0; i < nums.size(); i++) {
        if (left[i] == -1 && right[i] == -1) {
            root = nodes[i];
        } else if (left[i] != -1 && right[i] == -1) {
            nodes[left[i]]->right = nodes[i];
        } else if (left[i] == -1 && right[i] != -1) {
            nodes[right[i]]->left = nodes[i];
        } else if (nums[left[i]] > nums[right[i]]) {
            nodes[right[i]]->left = nodes[i];
        } else {
            nodes[left[i]]->right = nodes[i];
        }
    }
    return root;
}
